#include <stdio.h>
#include "LinkStack.h"
#include "LinkQueue.h"

//两个栈实现一个队列
struct MyQueue
{
    LStack *s1;
    LStack *s2;
};
typedef struct MyQueue MQueue;

void InitMyQueue(MQueue *q)
{
    q->s1 = InitStack();
    q->s2 = InitStack();
}

//入队列
void MyQPush(MQueue *q,ElementType element)
{
    while(IsStackEmpty(q->s2) == false)
    {
        SPush(q->s1,*GetSTop(q->s2));
        SPop(q->s2);
    }
    SPush(q->s1,element);
}

bool IsMQueueEmpty(MQueue *q)
{
    return IsStackEmpty(q->s1)&&IsStackEmpty(q->s2);
}

//出队列
void MyQPop(MQueue *q)
{
    if(IsMQueueEmpty(q) == true)
    {
        printf("队列为空！\n");
        return;
    }
        
    while(IsStackEmpty(q->s1) == false)
    {
        SPush(q->s2,*GetSTop(q->s1));
        SPop(q->s1);
    }
    SPop(q->s2);
}

//获取队头元素
ElementType* GetMQueueTop(MQueue *q)
{
    if(IsMQueueEmpty(q) == true)
    {
        printf("队列为空！\n");
        return NULL;
    }
        
    while(IsStackEmpty(q->s1) == false)
    {
        SPush(q->s2,*GetSTop(q->s1));
        SPop(q->s1);
    }
    return GetSTop(q->s2);
}

void ClearMQueue(MQueue *q)
{
    ClearLStack(q->s1,NULL);
    ClearLStack(q->s2,NULL);
}




//两个队列实现一个栈
struct MyStack
{
    LQueue *q1;
    LQueue *q2;
    //用来存储栈顶元素的数据
    ElementType data;
};
typedef struct MyStack MStack;

void InitMStack(MStack *s)
{
    s->q1 = InitLQueue();
    s->q2 = InitLQueue();
}

//入栈
void MSPush(MStack *s,ElementType element)
{
    if(IsQueueEmpty(s->q1) == true)
    {
        QPush(s->q2,element);
    }
    else
    {
        QPush(s->q1,element);
    }
}

//出栈
ElementType* MSPop(MStack *s)
{
    //判断两条队列是否都为空
    if(IsQueueEmpty(s->q1) == true && IsQueueEmpty(s->q2) == true)
    {
        printf("栈为空！\n");
        return NULL;
    }
    //q1为空
    else if(IsQueueEmpty(s->q1) == true)
    {
        //把q2 队列中的数据放到q1 队列中，只剩一个，这剩下的一个就是栈顶元素
        while(GetQueueLen(s->q2) > 1)
        {
            //压入q1
            QPush(s->q1,*GetQFront(s->q2));
            //从q2弹出
            QPop(s->q2);
        }
        //获取栈顶元素
        s->data = *GetQFront(s->q2);
        //弹出栈顶元素
        QPop(s->q2);
    }   
    else
    {
        //q2为空
        while(GetQueueLen(s->q1) > 1)
        {
            //压入q2
            QPush(s->q2,*GetQFront(s->q1));
            //从q2弹出
            QPop(s->q1);
        }
        s->data = *GetQFront(s->q1);
        QPop(s->q1);
    }
    return &s->data; 
}

bool IsMStackEmpty(MStack *s)
{
    return IsQueueEmpty(s->q1) && IsQueueEmpty(s->q2);
}

void ClearMStack(MStack *s)
{
    ClearLQueue(s->q1,NULL);
    ClearLQueue(s->q2,NULL);
}


// int main()
// {
    // MQueue q;
    // InitMyQueue(&q);

    // for(long i = 0; i <= 10; i++)
    // {
    //     MyQPush(&q,(void*)i);
    // }

    // while(IsMQueueEmpty(&q) == false)
    // {
    //     printf("%ld ",(long)*GetMQueueTop(&q));
    //     MyQPop(&q);
    // }
    // printf("\n");


    // MStack s;
    // InitMStack(&s);

    // for(long i = 0; i <= 10; i++)
    // {
    //     MSPush(&s,(void*)i);
    // }

    // while(IsMStackEmpty(&s) == false)
    // {
    //     printf("%ld ",(long)*MSPop(&s));
    // }
    // printf("\n");

//     return 0;
// }